Addition

過去數位系統

* half adder > full adder
* one bit的full adder > 用ripple carry的方式讓它們連接在一起
ripple carry adder(處理multiple bit)

發現ripple carry adder它的performance可能不太好

也因此新的adder如: 
carry-lookahead adder
carry-select adder

ripple carry adder的潛在問題

有一個ripple carry是1
我們的carry會一步一步從低位元往前傳 傳到高位元
整個運算的時間會因此而拉長(尤其是高位元的加法)

用軟體complexity的概念來思考 ripple carry adder它的complexity是O(n)

例子

有N個one bit 的ALU
每一個低位元的ALU都會產生一個carry往前傳遞
傳遞之後又會造成前面高位元的bit又會產生carry
需要再往更高位元傳遞的話
那麼將會導致我們的delay會達到N倍的delay
也就是N個stage

carry-lookahead adder設計概念

希望能夠平行的讓每一個bit都可以很快的拿到它的carry in
就可以把它的carry out以及它的sum都計算出來

最關鍵的事情:
讓每一個bit它們彼此之間carry的dependence carry的相依性能夠移除

每一個one bit的adder都可以直接的取得它自己的carry
去完成運算

要能夠產生這些carry它的電路長什麼樣子呢?

Carry Computation Circuit

產生carry也就是進位
一定必須要任兩個人為1

所以要計算carry就是(A*B)+(A*C)+(B*C)
* -> AND
+ -> OR

Cin0已知
先把Cin2和Cin1方程式寫出來
再把Cin1帶入Cin2
然後化簡

經過整理的方程式:
1.有AB做and的運算
2.AB做or的運算
3.還有一個方程式會跟Cin有關係

定義兩個名詞

1.Generate

Ai*Bi

在第i個bit裡面它的input
A跟B如果同時為1的話
那麼gi就會是1

某一個bit i
它的兩個input A跟B都為1的話
那麼保證它一定會產生出一個carry out

這carry out是怎麼產生出來的

是透過A跟B做相加
然後自然而然就一定會有一個carry out

2.Propagate

Ai + Bi
Ai跟Bi這兩個input第i個bit
假設它們兩個有其中一個為1
那麼pi就會是1

如果當pi為1的時候
假如第i個bit它的carry in為1的話
再配上Ai跟Bi裡面其中有一個人是1
自然而然我們一定也會有carry out

這個carry out就意義上來看

好像是我有1個carry in進來
透過了A跟B
因為這兩個其中一個為1
就可以把這個carry往下一級傳遞出去
因此我們把它叫做Propagate傳遞

舉例

第0個bit的carry out = 第1個bit它的carry in

1.
可以是第0個bit自己產生出來的
也就是說A0跟B0同時為1
那麼自然而然就一定會有carry out

2.
或是A0跟B0它們兩個人至少有一個人為1
且我們的carry in(Cin0)也剛好是1的話
那麼第0個bit一樣也會產生carry out

第1個bit它的carry out = 第2個bit它的carry in

1.
可能是第一個bit自己產生出來的

2.
或是第0個bit產生了
透過第1個bit把它propagate傳遞出去

3.
或是p1,p0同時都為1
  也就是說A1,B1有一個人為1
  A0,B0也有一個人為1
在這樣的情況之下假設最前面的Cin0也是1的話

..

透過剛才的分析已經知道如何去產生carry out的Boolean equation

而且完全只會跟
1.generate
2.propagate
3.以及最前面的carry in有關

所以我們不再需要依賴前一級的carry out

只要用我們剛才前面所產生的Boolean equation
就可以設計出一個新的電路

可以幫助我們去把carry lookahead
也就是把carry一次的產生出來

問題:

有注意到方程式的長度越來越長
因此不可能一口氣的直接去設計出第31個bit的carry

它的效能反而會變得很糟糕

解決:

用了4個bit讓它變成一組

分類:

這4個bit一組
又有不同的組合方式
1."cascaded carry look-ahead adder"
2."multiple level carry look-ahead adder"

cascaded carry look-ahead adder

底下還是加法器
而上面我們有4個4-bit的carry look ahead unit
它們會做的事情就是去計算carry

注意:
它們一次只能算出4個bit的carry

所以假設一開始我們給定了propargate以及generate還有Cin
當我們給定了這些值之後

最底下的
也就是最後一個4bit的carry look ahead unit
它的值都已經準備好了

因為這邊c0已經有了
於是乎我們就可以去計算所謂的carry out
在這邊的carry out
也就是第1個bit到第4個bit它的carry in

計算完成了之後
這邊的第4個bit的carry in就會傳到下一級

依此類推 我們就可以把carry 4個bit 4個bit的算出來

結論

cascaded carry look-ahead adder跟ripple carry adder有一點點像

在這裡我們會傳遞C4, C8, C12
所以實際上每一個4bit carry look-ahead unit
它依然需要等待前一級的人
(當它把carry 計算完成之後
它才能夠正確的開始計算
然後把它的carry算出來
傳給底下的加法器
讓它去完成完整的運算)

complexity

O(n/4)
從演算法的複雜度角度來看
O(n)後面除以一個constant 有除等於沒除
意思是說 其實它的complexity還是O(n)

multiple level的carry lookahead

我們有沒有辦法讓它的carry不需要一個一個傳遞(4 bit)
而直接透過某一種機制讓它一口氣的去計算完成

就好像是我們上面又有新的電路
而這新的電路它會幫助我們去把carry給計算出來

以至於在這底下的每個carry lookahead unit就能夠同時的工作
也就能夠同時的產生出carry的output出來
傳給底下的加法器
讓它最後一口氣拿到所有的carry
一次的把加法計算完成

由更高層次的觀點看，4個bit一組當成一個大單位Unit 當一個carry in進來，到底會不會有carry out呢?

分析低層次的boolean equation
紅色:
  代表能夠在Unit中自行產生(即使carry in為0，他 也有可能有能力產生出carry out)
紫色:
  能夠在Unit中傳輸(一個carry in進來能傳到carry out)
藍色:
  Cin0

比較

在一個抽象層級
把高層次觀點的 Cin4 = G + ( P * Cin0 )
和低層次的 Cin1比較
發現竟然是一樣的!!!

思考

下一個問題是這個大寫的G跟大寫的P該如何產生呢
第三個bit的carry out
大寫的G:紅色的部分
大寫的P:紫色的部分

有一點點遞迴的感覺

這個大寫的G跟大寫的P
將會傳遞給更上層的人
而這更上層的人它的Boolean equation其實跟我們長的是一模一樣的
只是它的input吃的是大寫的G跟大寫的P

大P大G其實原本就是這4個bits一組裡面最高位元
也就是第3個bit它的carry out
把它第三個bit的carry out進一步的來看
它要如何的去propagate以及如何的去generate它的carry
如此一來我們就會產生出大P跟大G

可以進一步接到更上一層的carry lookahead unit

更上一層的carry lookahead unit
它的Boolean equation跟我們下面這一層的Boolean equation
是一模一樣的

multiple level的carry lookahead重點!!!

每一個單位都會分別產生出一個大寫的P跟大寫的G
而大寫的P跟大寫的G將會往上傳遞

在這裡同學看到更上一層的carry lookahead unit
請注意這個carry lookahead unit
它的Boolean function其實跟底下的Boolean function是一模一樣的

既然是一模一樣的
硬體其實就可以重複的使用

這下面的人產生的大P跟大G
其實是不需要等待這個c0的

它可以一口氣產生出C4, C8跟C12
有了c4, c8, c12再配上了c0
我們就可以把所有的carry通通產生出來
於是乎加法就完成了

complexity

是一個tree structure
O(log n)

缺點

實際上應用到的硬體資源會比較多
可是多了這一些
卻能夠讓我們的運算速度變很快

carry-select adder

有錢人的作法

既然我們並不知道它的carry是0還是1

我就放兩個加法器在這邊 一個加法器我們強迫給它carry是0 另外一個加法器強迫給它carry是1

代表的是如果我要賭博
我就兩邊通通都押
那麼我們得到的結果一定會有一個是對的

於是乎我們就用MUX去選

我們只要前一級計算完了之後
把前一級的carry拿過來加到這個MUX
選出來的值就是我們要的

如果我們下面還有一級加法器的話 我這output出來的結果又要再接到MUX去選

還是有ripple的現象
還是要一級一級的去傳

我們今天的MUX其實要做的是一個2選1
我們看到SUM的結果有兩個我們要選出一個
依據我們的carry out是0還是1來選的
2選1的MUX其實電路設計是很簡單的
意思是說它的計算時間會非常的短暫

演算法的複雜度的角度來看

它的big O前面的這個constant它的常數非常的小
所以實際上我們利用這樣子的一個方式去做出來的加法器運算的結果